1. Field of the Invention
This invention relates generally to transactional memory computer systems and, more specifically, to a system and method for using software contention management to reduce abort rates in hardware-based transactional memory systems, such as those implementing speculative lock elision.
2. Description of the Related Art
Due to the complexity and energy concerns of modern processors, traditional approaches to boosting CPU performance have become difficult and ineffective. Instead of attempting to drive up clock speeds, computer architects are increasingly turning to multi-threading techniques such as symmetric multi-threading or multi-core architectures. In order to leverage these new architectures, software engineers must write applications that execute using multiple concurrent threads of execution. Unfortunately, correct multi-threaded programming is notoriously difficult using traditional language constructs.
Shared-memory systems allow multiple threads to access and operate on the same shared memory locations. To maintain consistency, threads must often execute a series of instructions as one atomic block, or critical section. In these cases, care must be taken to ensure that other threads do not observe memory values from a partial execution of such a block. To ensure correctness, threads may use traditional constructs, such as mutual exclusion and locks, to exclude all other threads from concurrent access to a critical section protected by the same lock(s). For example, no thread may enter a critical section without holding the section's lock. While it does, all other threads wishing to execute a critical section protected by the same lock must await the lock's release and acquire it before proceeding. The pitfalls of these constructs are numerous and well known. They include dead-lock, race conditions, priority inversions, software complexity, and performance limitations.
Alternatively, it may be possible to increase parallelism by allowing multiple threads to execute critical sections protected by the same lock concurrently if the executions do not rely on overlapping memory locations. Doing so may increase performance and mitigate many of the pitfalls normally associated with traditional locking mechanisms. However, such interleaved executions are not guaranteed to be correct.
Transactional memory is a mechanism that can be leveraged to enable concurrent and correct execution of a critical section by multiple threads. Transactional memory allows a thread to execute a block of instructions as a transaction, that is, either completely and atomically or not at all. The instructions are executed and then either “committed”, allowing the aggregate effect to be seen by all other threads, or “aborted”, allowing no effect to be seen. A transaction that has committed successfully may be said to have “succeeded”. If an attempt to execute a transaction aborts, it may be retried.
Speculative lock-elision (SLE) and similar hardware-based, implicit speculative execution techniques (e.g., Transactional Lock Removal, Speculative Synchronization, etc.) may automatically and transparently convert existing, lock-based, critical sections to transactions by recognizing instructions normally found at the start of each critical section and executing those critical sections speculatively and non-exclusively. Thus, rather than acquiring locks and executing serially, multiple threads, even of applications that are SLE-unaware, may concurrently execute critical sections protected by the same lock. However, if a data conflict occurs during speculative execution, a transaction may be aborted. For example, if a transaction speculatively reads a value from memory, and that value is modified before the transaction commits, then the transaction may be aborted.
In addition to conflict aborts, aborts may also result when SLE implementations misidentify sections of code as critical sections that should be executed as transactions. For example, an atomic compare-and-swap (CAS) instruction is often used to acquire a lock at the beginning of a critical section. Currently available SLE implementations may switch to speculative execution mode whenever execution encounters a CAS instruction. However, some CAS instructions are executed for purposes other than lock acquisition. In such cases, the SLE implementation would mistakenly identify the CAS instruction as signifying the start of a critical section and enter speculative execution mode. Since no corresponding instruction sequence exists to “commit” the misidentified critical section, the speculative execution would eventually fail. In some cases, the SLE implementation may even reattempt the section using speculative execution. Such attempts are futile and represent wasted system resources and degraded overall system performance.